#pragma once

#include "iostream"
#include "vector"
#include "algorithm"

using namespace std;
/*HJJ QQ479287006
 *输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。

 

为了让您更好地理解问题，以下面的二叉搜索树为例：
我们希望将这个二叉搜索树转化为双向循环链表。链表中的每个节点都有一个前驱和后继指针。对于双向循环链表，第一个节点的前驱是最后一个节点，最后一个节点的后继是第一个节点。

下图展示了上面的二叉搜索树转化成的链表。“head” 表示指向链表中有最小元素的节点。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/er-cha-sou-suo-shu-yu-shuang-xiang-lian-biao-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/er-cha-sou-suo-shu-yu-shuang-xiang-lian-biao-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * */
//todo 哈哈这道题确实写不出来 我日了
class Node {
public:
    int val;
    Node *left;
    Node *right;

    Node() {}

    Node(int _val) {
        val = _val;
        left = NULL;
        right = NULL;
    }

    Node(int _val, Node *_left, Node *_right) {
        val = _val;
        left = _left;
        right = _right;
    }
};

//Node *head = nullptr;
//Node *pre = nullptr;
//
//void dfs(Node *cur) {
//    // 递归结束条件
//    if (!cur) return;
//    dfs(cur->left);
//    // 如果pre为空，就说明是第一个节点，头结点，然后用head保存头结点，用于之后的返回
//    if (!pre) head = cur;
//        // 如果不为空，那就说明是中间的节点。并且pre保存的是上一个节点，
//        // 让上一个节点的右指针指向当前节点
//    else if (pre) pre->right = cur;
//    // 再让当前节点的左指针指向父节点，也就连成了双向链表
//    cur->left = pre;
//    // 保存当前节点，用于下层递归创建
//    pre = cur;//操 这里的用全局变量保存了 我傻逼了 一直用参数 传过去然后 递归回来就恢复环境了  我原来 dfs（node ，pre）
//    //其实还是中序遍历
//
//    dfs(cur->right);
//}
//
//// 中序遍历吧  递归返回头结点
//Node *treeToDoublyList(Node *root) {
//    if (!root) return root;
//    dfs(root);
//
//    // 题目要求头尾连接
//    head->left = pre;
//    pre->right = head;
//    // 返回头节点
//    return head;
//}





Node *head = nullptr;
Node *pre = nullptr;

//中序遍历
void treeToDoublyList_r(Node *root) {

    if (!root)
        return;

    treeToDoublyList_r(root->left);

    if (!head) {
        head = root;
    } else {
        if (pre) {
            // root->left=pre;
            pre->right = root;
        }
        root->left = pre;
        // pre=root;
    }
    pre = root;
    treeToDoublyList_r(root->right);

}

Node *treeToDoublyList(Node *root) {
    treeToDoublyList_r(root);
    head->left = pre;
    pre->right = head;
    return head;
}